`:top
In `F33f`_`[mathematics`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Mathematics]`_`f and `F33f`_`[optimization`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Optimization]`_`f, a `!pseudo-Boolean function`! is a `F33f`_`[function`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Function_(mathematics)]`_`f of the form
f : B n → → R , {\\displaystyle f:\\mathbf {B} ^{n}\\to \\mathbb {R} ,}
where `!B`! = {0, 1} is a `*`F33f`_`[Boolean domain`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Boolean_domain]`_`f`* and n is a nonnegative `F33f`_`[integer`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Integer]`_`f called the `F33f`_`[arity`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Arity]`_`f of the function. A `F33f`_`[Boolean function`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Boolean_function]`_`f is then a special case, where the values are also restricted to 0 or 1.
>>Contents
• `F0af`_`[Representations`#representations]`_`f
• `F0af`_`[Optimization`#optimization]`_`f
• `F0af`_`[Submodularity`#submodularity]`_`f
• `F0af`_`[Roof Duality`#roof-duality]`_`f
• `F0af`_`[Quadratizations`#quadratizations]`_`f
• `F0af`_`[Polynomial Compression Algorithms`#polynomial-compression-algorithms]`_`f
• `F0af`_`[See also`#see-also]`_`f
• `F0af`_`[Notes`#notes]`_`f
• `F0af`_`[References`#references]`_`f
-─
>>Representations
Any pseudo-Boolean function can be written uniquely as a `F33f`_`[multi-linear`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Multi-linear]`_`f polynomial:`:cite-ref-1[`F5bf`_`[1`#cite-note-1]`_`f]`:cite-ref-2[`F5bf`_`[2`#cite-note-2]`_`f]
f ( x ) = a + ∑ ∑ i a i x i + ∑ ∑ i < j a i j x i x j + ∑ ∑ i < j < k a i j k x i x j x k + … … {\\displaystyle f({\\boldsymbol {x}})=a+\\sum _{i}a_{i}x_{i}+\\sum _{i<j}a_{ij}x_{i}x_{j}+\\sum _{i<j<k}a_{ijk}x_{i}x_{j}x_{k}+\\ldots }
The `!degree`! of the pseudo-Boolean function is simply the degree of the `F33f`_`[polynomial`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Polynomial]`_`f in this representation.
In many settings (e.g., in `F33f`_`[Fourier analysis of pseudo-Boolean functions`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Analysis_of_Boolean_functions]`_`f), a pseudo-Boolean function is viewed as a function f {\\displaystyle f} that maps { − − 1 , 1 } n {\\displaystyle \\{-1,1\\}^{n}} to R {\\displaystyle \\mathbb {R} } . Again in this case we can uniquely write f {\\displaystyle f} as a multi-linear polynomial: f ( x ) = ∑ ∑ I ⊆ ⊆ [ n ] f ^ ^ ( I ) ∏ ∏ i ∈ ∈ I x i , {\\displaystyle f(x)=\\sum _{I\\subseteq [n]}{\\hat {f}}(I)\\prod _{i\\in I}x_{i},} where f ^ ^ ( I ) {\\displaystyle {\\hat {f}}(I)} are Fourier coefficients of f {\\displaystyle f} and [ n ] = { 1 , . . . , n } {\\displaystyle [n]=\\{1,...,n\\}} .
>>Optimization
Minimizing (or, equivalently, maximizing) a pseudo-Boolean function is `F33f`_`[NP-hard`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=NP-hard]`_`f. This can easily be seen by formulating, for example, the `F33f`_`[maximum cut`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Maximum_cut]`_`f problem as maximizing a pseudo-Boolean function.`:cite-ref-boros2002-3-0[`F5bf`_`[3`#cite-note-boros2002-3]`_`f]
>>>Submodularity
The `F33f`_`[submodular set functions`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Submodular_set_function]`_`f can be viewed as a special class of pseudo-Boolean functions, which is equivalent to the condition
f ( x ) + f ( y ) ≥ ≥ f ( x ∧ ∧ y ) + f ( x ∨ ∨ y ) , ∀ ∀ x , y ∈ ∈ B n . {\\displaystyle f({\\boldsymbol {x}})+f({\\boldsymbol {y}})\\geq f({\\boldsymbol {x}}\\wedge {\\boldsymbol {y}})+f({\\boldsymbol {x}}\\vee {\\boldsymbol {y}}),\\;\\forall {\\boldsymbol {x}},{\\boldsymbol {y}}\\in \\mathbf {B} ^{n}\\,.}
This is an important class of pseudo-boolean functions, because they can be `F33f`_`[minimized in polynomial time`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Submodular_set_function]`_`f. Note that minimization of a submodular function is a polynomially solvable problem independent on the presentation form, for e.g. pesudo-Boolean polynomials, opposite to maximization of a submodular function which is NP-hard, Alexander Schrijver (2000).
>>>Roof Duality
If `*f`* is a quadratic polynomial, a concept called `*roof duality`* can be used to obtain a lower bound for its minimum value.`:cite-ref-boros2002-3-1[`F5bf`_`[3`#cite-note-boros2002-3]`_`f] Roof duality may also provide a partial assignment of the variables, indicating some of the values of a minimizer to the polynomial. Several different methods of obtaining lower bounds were developed only to later be shown to be equivalent to what is now called roof duality.`:cite-ref-boros2002-3-2[`F5bf`_`[3`#cite-note-boros2002-3]`_`f]
>>>Quadratizations
If the degree of `*f`* is greater than 2, one can always employ `*reductions`* to obtain an equivalent quadratic problem with additional variables. One possible reduction is
− − x 1 x 2 x 3 = min z ∈ ∈ B z ( 2 − − x 1 − − x 2 − − x 3 ) {\\displaystyle \\displaystyle -x_{1}x_{2}x_{3}=\\min _{z\\in \\mathbf {B} }z(2-x_{1}-x_{2}-x_{3})}
There are other possibilities, for example,
− − x 1 x 2 x 3 = min z ∈ ∈ B z ( − − x 1 + x 2 + x 3 ) − − x 1 x 2 − − x 1 x 3 + x 1 . {\\displaystyle \\displaystyle -x_{1}x_{2}x_{3}=\\min _{z\\in \\mathbf {B} }z(-x_{1}+x_{2}+x_{3})-x_{1}x_{2}-x_{1}x_{3}+x_{1}.}
Different reductions lead to different results. Take for example the following `F33f`_`[cubic polynomial`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Cubic_function]`_`f:`:cite-ref-kahl2011-4-0[`F5bf`_`[4`#cite-note-kahl2011-4]`_`f]
f ( x ) = − − 2 x 1 + x 2 − − x 3 + 4 x 1 x 2 + 4 x 1 x 3 − − 2 x 2 x 3 − − 2 x 1 x 2 x 3 . {\\displaystyle \\displaystyle f({\\boldsymbol {x}})=-2x_{1}+x_{2}-x_{3}+4x_{1}x_{2}+4x_{1}x_{3}-2x_{2}x_{3}-2x_{1}x_{2}x_{3}.}
Using the first reduction followed by roof duality, we obtain a lower bound of −3 and no indication on how to assign the three variables. Using the second reduction, we obtain the (tight) lower bound of −2 and the optimal assignment of every variable (which is ( 0 , 1 , 1 ) {\\displaystyle {(0,1,1)}} ).
>>>Polynomial Compression Algorithms
Consider a pseudo-Boolean function f {\\displaystyle f} as a mapping from { − − 1 , 1 } n {\\displaystyle \\{-1,1\\}^{n}} to R {\\displaystyle \\mathbb {R} } . Then f ( x ) = ∑ ∑ I ⊆ ⊆ [ n ] f ^ ^ ( I ) ∏ ∏ i ∈ ∈ I x i . {\\displaystyle f(x)=\\sum _{I\\subseteq [n]}{\\hat {f}}(I)\\prod _{i\\in I}x_{i}.} Assume that each coefficient f ^ ^ ( I ) {\\displaystyle {\\hat {f}}(I)} is integral. Then for an integer k {\\displaystyle k} the problem P of deciding whether f ( x ) {\\displaystyle f(x)} is more or equal to k {\\displaystyle k} is NP-complete. It is proved in `:cite-ref-crowston2011-5-0[`F5bf`_`[5`#cite-note-crowston2011-5]`_`f] that in polynomial time we can either solve P or reduce the number of variables to O ( k 2 log k ) . {\\displaystyle O(k^{2}\\log k).} Let r {\\displaystyle r} be the degree of the above multi-linear polynomial for f {\\displaystyle f} . Then `:cite-ref-crowston2011-5-1[`F5bf`_`[5`#cite-note-crowston2011-5]`_`f] proved that in polynomial time we can either solve P or reduce the number of variables to r ( k − − 1 ) {\\displaystyle r(k-1)} .
>>See also
• `F33f`_`[Boolean function`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Boolean_function]`_`f
• `F33f`_`[Quadratic pseudo-Boolean optimization`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Quadratic_pseudo-Boolean_optimization]`_`f
>>Notes
`:cite-note-1`!1.`! `F0af`_`[↑`#cite-ref-1]`_`f `:citerefhammerrosenbergrudeanu1963`aHammer, P.L.; Rosenberg, I.; Rudeanu, S. (1963). "On the determination of the minima of pseudo-Boolean functions". `*Studii și cercetări matematice`* (in Romanian) (14): 359–364. `F33f`_`[ISSN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISSN_(identifier)]`_`f 0039-4068.
`:cite-note-2`!2.`! `F0af`_`[↑`#cite-ref-2]`_`f `:citerefhammerrudeanu1968`aHammer, Peter L.; Rudeanu, Sergiu (1968). `*Boolean Methods in Operations Research and Related Areas`*. Springer. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 978-3-642-85825-3.
`:cite-note-boros2002-3`!3.`! `F0af`_`[↑`#cite-ref-boros2002-3-0]`_`f `:citerefboroshammer2002`aBoros, E.; Hammer, P. L. (2002). "Pseudo-Boolean Optimization". `*`F33f`_`[Discrete Applied Mathematics`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Discrete_Applied_Mathematics]`_`f`*. `!123`! (1–3): 155–225. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1016/S0166-218X(01)00341-9. `F33f`_`[hdl`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Hdl_(identifier)]`_`f:2268/202427.
`:cite-note-kahl2011-4`!4.`! `F0af`_`[↑`#cite-ref-kahl2011-4-0]`_`f `:citerefkahlstrandmark2011`aKahl, F.; Strandmark, P. (2011). `*Generalized Roof Duality for Pseudo-Boolean Optimization`* (PDF). `F33f`_`[International Conference on Computer Vision`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=International_Conference_on_Computer_Vision]`_`f.
`:cite-note-crowston2011-5`!5.`! `F0af`_`[↑`#cite-ref-crowston2011-5-0]`_`f `:citerefcrowstonfellowsgutinjones2011`aCrowston, R.; Fellows, M.; Gutin, G.; Jones, M.; Rosamond, F.; Thomasse, S.; Yeo, A. (2011). "Simultaneously Satisfying Linear Equations Over GF(2): MaxLin2 and Max-r-Lin2 Parameterized Above Average". `*Proc. Of FSTTCS 2011`*. `F33f`_`[arXiv`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ArXiv_(identifier)]`_`f:1104.1135. `F33f`_`[Bibcode`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bibcode_(identifier)]`_`f:2011arXiv1104.1135C.
>>References
• `:citerefishikawa2011`aIshikawa, H. (2011). "Transformation of general binary MRF minimization to the first order case". `*`F33f`_`[IEEE Transactions on Pattern Analysis and Machine Intelligence`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=IEEE_Transactions_on_Pattern_Analysis_and_Machine_Intelligence]`_`f`*. `!33`! (6): 1234–1249. `F33f`_`[CiteSeerX`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=CiteSeerX_(identifier)]`_`f 10.1.1.675.2183. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1109/tpami.2010.91. `F33f`_`[PMID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=PMID_(identifier)]`_`f 20421673. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 17314555.
• `:citerefo-donnell2008`a`F33f`_`[O'Donnell, Ryan`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Ryan_O'Donnell_(computer_scientist)]`_`f (2008). "Some topics in analysis of Boolean functions". `*ECCC`*. `F33f`_`[ISSN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISSN_(identifier)]`_`f 1433-8092.
• `:citerefrotherkolmogorovlempitskyszummer2007`aRother, C.; Kolmogorov, V.; Lempitsky, V.; Szummer, M. (2007). `*Optimizing Binary MRFs via Extended Roof Duality`* (PDF). `F33f`_`[Conference on Computer Vision and Pattern Recognition`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Conference_on_Computer_Vision_and_Pattern_Recognition]`_`f.
• `:citerefschrijver2000`aSchrijver, Alexander (November 2000). "A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time". `*Journal of Combinatorial Theory`*. `!80`! (2): 346–355. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1006/jctb.2000.1989.
`c`F0af`_`[↑ Back to top`#top]`_`f`a